#pragma once
#include<iostream>
using namespace std;

enum Color
{
  RED,
  BLACK
};

template<class K,class V>
struct RBTreeNode
{
    RBTreeNode<K,V>* _left;
    RBTreeNode<K,V>* _right;
    RBTreeNode<K,V>* _parent;
    
    pair<K,V> _kv;
    Color _col;
    
    RBTreeNode(const pair<K, V>&kv)
    :_left(nullptr)
    ,_right(nullptr)
    ,_parent(nullptr)
    ,_kv(kv)
    ,_col(RED)
    {}
};

template<class K,class V>
class RBTree
{
    typedef RBTreeNode<K,V> Node;
public:
    bool Insert(const pair<K, V>& kv)
    {
        if(_root==nullptr)
        {
            _root=new Node(kv);
            return true;
        }
        
        Node* parent=nullptr;
        Node* cur=_root;
        
        while(cur)
        {
            if(cur->_kv.first<kv.first)
            {
                parent=cur;
                cur=cur->_right;
            }
            else if(cur->_kv.first>kv.first)
            {
                parent=cur;
                cur=cur->_left;
            }
            else
            {
                return false;
            }
        }
        cur=new Node(kv);
        cur->_col;//
        
        if(parent->_kv.first<kv.first)
        {
            parent->_right=cur;
            cur->_parent=parent;//将节点的父指针指向父亲
        }
        else
        {
            parent->_left=cur;
            cur->_parent=parent;//将节点的父指针指向父亲
        }
        
        return true;
    }
    
private:
    Node* _root=nullptr;
};

